평면 그래프

평면 그래프는 그래프 이론에서 중요한 연구 대상으로, 평면 상에 모든 꼭짓점과 변을 그릴 때, 변들이 서로 교차하지 않도록 그릴 수 있는 그래프를 의미한다. 이는 그래프를 평면에 어떻게 배치하느냐에 대한 위상적 성질을 다루며, 위상수학과 조합론의 관점에서 접근된다.

평면 그래프의 개념은 18세기 레온하르트 오일러가 다면체의 성질을 연구하며 발견한 오일러 공식과 함께 본격적으로 연구되기 시작했다. 오일러 공식은 연결된 평면 그래프에서 꼭짓점 수 V, 변 수 E, 면 수 F 사이에 V - E + F = 2라는 관계가 성립함을 보여준다. 이 공식은 평면 그래프의 기본적인 조합적 구조를 규정하는 핵심 성질이다.

평면 그래프의 대표적인 예로는 완전 그래프 K4, 완전 이분 그래프 K2,3, 그리고 모든 나무가 있다. 반면, 완전 그래프 K5와 완전 이분 그래프 K3,3은 평면 그래프가 될 수 없는 가장 기본적인 두 가지 그래프로, 쿠라토프스키 정리는 어떤 그래프가 평면 그래프인지 판별하는 근본적인 기준을 이 두 그래프를 이용해 제시한다.

평면 그래프의 평면성을 판정하는 것은 그래프 이론의 중요한 주제이다. 어떤 그래프가 평면 그래프인지 아닌지를 판별하는 방법에는 여러 가지가 있다.

가장 유명한 판정 기준은 쿠라토프스키 정리이다. 이 정리에 따르면, 어떤 그래프가 평면 그래프가 아니라는 것은 그 그래프가 완전 그래프 K5 또는 완전 이분 그래프 K3,3을 위상적으로 포함하는 것과 동치이다. 즉, 그래프의 어떤 부분 그래프를 반복적으로 변 위의 꼭짓점을 제거하는 방식으로 단순화했을 때 K5나 K3,3이 나오면 그 그래프는 평면 그래프가 아니다. 이 정리는 평면성에 대한 완전한 필요충분조건을 제공한다.

실제로 평면성을 검사하는 알고리즘도 개발되어 있다. 대표적인 알고리즘으로는 깊이 우선 탐색을 기반으로 하는 알고리즘이 있으며, 이는 선형 시간 내에 그래프의 평면성을 판정할 수 있다. 이러한 알고리즘들은 회로 설계나 네트워크 레이아웃과 같은 응용 분야에서 직접적으로 활용된다.

또한, 평면 그래프는 오일러 공식으로부터 유도되는 간단한 필요조건을 만족해야 한다. 연결된 평면 그래프에서 꼭짓점 수를 V, 변 수를 E, 면 수를 F라 할 때, V - E + F = 2가 성립한다. 이를 이용하면, 예를 들어 모든 꼭짓점의 차수가 3 이상인 연결된 평면 그래프는 E ≤ 3V - 6이라는 부등식을 만족해야 한다는 사실을 증명할 수 있다. 이 조건을 만족하지 않으면 그 그래프는 평면 그래프가 아님을 알 수 있다.

오일러 공식은 연결된 평면 그래프의 꼭짓점, 변, 면의 수 사이에 성립하는 기본적인 관계를 나타낸다. 공식은 V - E + F = 2로 표현되며, 여기서 V는 꼭짓점의 수, E는 변의 수, F는 면의 수를 의미한다. 이 공식은 평면 그래프의 구조에 대한 강력한 제약 조건을 제공하며, 그래프가 평면일 수 있는지 여부를 판단하는 데 유용하게 활용된다.

이 공식은 레온하르트 오일러의 이름을 따서 명명되었으며, 위상수학적 관점에서 다면체에 대한 연구에서 비롯되었다. 오일러 공식은 평면 그래프의 핵심 성질 중 하나로, 이를 통해 평면 그래프의 변의 최대 개수나 면의 수와 같은 여러 중요한 결론을 도출할 수 있다. 예를 들어, 모든 면이 삼각형으로 이루어진 최대 평면 그래프에서는 E = 3V - 6이라는 관계가 성립함을 보일 수 있다.

오일러 공식은 평면 그래프의 필수 불가결한 도구로서, 쿠라토프스키 정리나 4색 정리와 같은 더 심오한 정리들을 증명하는 데 기초가 되기도 한다. 또한 이 공식은 평면 그래프가 아닌 다른 곡면에 그려진 그래프로 일반화되기도 하여, 위상 그래프 이론의 중요한 출발점이 된다.

외평면 그래프는 평면 그래프의 특수한 종류로, 모든 꼭짓점이 그래프의 외부 면 하나와 인접하도록 평면에 그릴 수 있는 그래프를 말한다. 즉, 그래프를 평면에 그렸을 때, 모든 꼭짓점들이 하나의 공통된 외부 면의 경계 위에 위치하게 할 수 있다. 이러한 특성 때문에 외평면 그래프는 평면 그래프보다 더 강한 제약 조건을 가지며, 일반적인 평면 그래프보다 구조적으로 단순한 경우가 많다.

외평면 그래프는 평면성을 판정하는 중요한 기준 중 하나이다. 모든 외평면 그래프는 평면 그래프이지만, 그 역은 성립하지 않는다. 예를 들어, 완전 그래프 K4는 평면 그래프이지만, 모든 꼭짓점이 하나의 면에만 인접하도록 그릴 수 없기 때문에 외평면 그래프는 아니다. 외평면 그래프의 대표적인 예로는 모든 사이클이 외부 면을 공유하도록 그릴 수 있는 그래프나, 특정 조건을 만족하는 나무의 확장 형태 등이 있다.

이러한 그래프는 여러 알고리즘 문제에서 유리한 성질을 보인다. 예를 들어, 일반적인 평면 그래프에 비해 그래프 색칠 문제나 최대 독립 집합 문제 등을 더 효율적으로 해결할 수 있는 경우가 있다. 이는 외평면 그래프가 가지는 단순한 위상적 구조 덕분이다.

외평면 그래프의 주요 성질을 요약하면 다음과 같다.

최대 평면 그래프는 주어진 꼭짓점 수를 가진 평면 그래프 중에서 변의 수가 최대인 그래프를 말한다. 모든 꼭짓점이 삼각형을 이루도록 연결되어 있으며, 이는 그래프가 평면 위에 그려졌을 때 모든 면이 삼각형인 상태와 동치이다. 따라서 최대 평면 그래프는 삼각분할 그래프라고도 불린다.

이러한 그래프는 오일러 공식을 활용하여 그 구조를 명확히 분석할 수 있다. 연결된 최대 평면 그래프에서 꼭짓점 수를 V, 변의 수를 E, 면의 수를 F라고 할 때, 모든 면이 삼각형이므로 3F = 2E의 관계가 성립한다. 이를 오일러 공식 V - E + F = 2에 대입하면, 변의 수 E는 꼭짓점 수 V에 대해 E = 3V - 6이라는 중요한 공식을 얻을 수 있다. 또한, 면의 수는 F = 2V - 4가 된다.

최대 평면 그래프의 대표적인 예로는 완전 그래프 K4가 있다. K4는 4개의 꼭짓점을 가진 최대 평면 그래프이며, 평면 위에 변이 교차하지 않게 그릴 수 있는 가장 큰 완전 그래프이다. 반면, 5개의 꼭짓점을 가진 완전 그래프 K5는 쿠라토프스키 정리에 의해 평면 그래프가 아님을 알 수 있다. 이는 최대 평면 그래프가 평면 그래프의 한계를 보여주는 사례가 된다.

최대 평면 그래프의 개념은 회로 설계나 지도 작성과 같은 응용 분야에서 중요한 기준이 된다. 예를 들어, 평면 상에 배치해야 하는 요소들 사이의 연결을 최대한 많이 만들면서도 선이 교차하지 않도록 설계할 때, 이론적 한계를 제공하기 때문이다.

삼각분할 그래프는 평면 그래프의 한 종류로, 모든 면이 삼각형인 그래프를 의미한다. 여기서 '면'이란 그래프를 평면에 그렸을 때 변들로 둘러싸인 영역을 말하며, 바깥쪽의 무한한 영역인 외부 면도 포함한다. 따라서 삼각분할 그래프는 모든 면, 즉 내부 면과 외부 면 모두가 정확히 세 개의 변으로 둘러싸여 있다.

이러한 그래프는 최대 평면 그래프와 밀접한 관련이 있다. 연결된 평면 그래프에서 더 이상 변을 추가하면 평면성을 잃게 될 때, 그 그래프를 최대 평면 그래프라고 한다. 모든 최대 평면 그래프는 삼각분할 그래프이며, 그 역도 성립한다. 즉, 꼭짓점이 3개 이상인 연결된 평면 그래프가 삼각분할 그래프인 것과 최대 평면 그래프인 것은 동치이다. 이는 그래프가 평면성을 유지하면서 가질 수 있는 최대한의 변의 수를 가진 구조를 의미한다.

삼각분할 그래프는 오일러 공식과 결합하여 여러 중요한 조합적 성질을 도출하는 데 활용된다. 예를 들어, 모든 면이 삼각형이므로 각 변은 정확히 두 개의 면에 인접한다는 사실을 이용하면, 면의 수 F와 변의 수 E 사이에 3F = 2E라는 관계식을 얻을 수 있다. 이 관계식을 오일러 공식 V - E + F = 2와 연립하면, 꼭짓점 수 V가 3 이상일 때 변의 수 E = 3V - 6, 면의 수 F = 2V - 4라는 공식을 유도할 수 있다. 이는 삼각분할 그래프의 기본적인 수치적 특성을 보여준다.

이러한 성질은 그래프 이론과 위상수학에서 그래프의 구조를 분석하는 데 유용하게 쓰인다. 또한, 삼각분할은 계산기하학에서 표면을 단순한 요소(삼각형)로 분할하여 복잡한 기하학적 객체를 표현하거나 처리하는 데 널리 사용되는 기법이기도 하다.

쿠라토프스키 정리는 그래프 이론에서 어떤 그래프가 평면 그래프인지 아닌지를 판별하는 근본적인 기준을 제공하는 중요한 정리이다. 이 정리는 폴란드의 수학자 카지미에시 쿠라토프스키에 의해 1930년에 증명되었다. 이 정리에 따르면, 어떤 유한 그래프가 평면 그래프가 아니기 위한 필요충분조건은 그 그래프가 완전 그래프 K5 또는 완전 이분 그래프 K3,3을 위상적으로 포함하는 것이다.

여기서 '위상적으로 포함한다'는 것은 주어진 그래프가 K5 또는 K3,3을 부분 그래프로 가지거나, 또는 이들 그래프의 변 위에 차수가 2인 추가 꼭짓점들을 삽입하여 얻을 수 있는 그래프를 포함한다는 의미이다. 이러한 변환을 분할이라고 하며, 분할을 통해 얻은 그래프는 원래 그래프와 위상적으로 동일하다고 본다. 따라서 쿠라토프스키 정리는 평면 그래프가 아닌 모든 그래프의 핵심 구조 속에 반드시 K5 또는 K3,3의 형태가 숨어있다고 말할 수 있다.

이 정리의 중요성은 평면성 판별이라는 복잡한 문제를 두 가지 구체적이고 잘 알려진 그래프의 존재 여부로 환원시켰다는 점에 있다. K5는 5개의 꼭짓점이 모두 서로 연결된 그래프이며, K3,3은 두 개의 3개 꼭짓점 집합으로 구성되어 한 집합의 모든 꼭짓점이 다른 집합의 모든 꼭짓점과 연결된 그래프이다. 이 두 그래프는 가장 작은 비평면 그래프의 예시로, 이들의 비평면성은 직접 증명할 수 있다.

쿠라토프스키 정리는 이론적 중요성뿐만 아니라 평면성 검사 알고리즘을 설계하는 데에도 기초가 된다. 많은 알고리즘들은 주어진 그래프에서 K5 또는 K3,3의 위상적 복사본을 찾거나, 그 존재 가능성을 체계적으로 배제하는 방식으로 작동한다. 이로 인해 이 정리는 조합론과 이산수학의 여러 분야에서 필수적인 도구로 자리 잡았다.

완전 그래프 K5와 완전 이분 그래프 K3,3은 평면 그래프가 될 수 없는 가장 기본적이고 중요한 예시이다. 이 두 그래프는 쿠라토프스키 정리의 핵심 요소로, 어떤 그래프가 평면 그래프가 아니라는 것을 판별하는 데 결정적인 역할을 한다.

K5는 5개의 꼭짓점을 가지며, 모든 서로 다른 두 꼭짓점 사이에 변이 존재하는 그래프이다. 즉, 5개의 꼭짓점이 서로 완전히 연결되어 있다. K3,3은 두 개의 집합으로 나뉜 6개의 꼭짓점을 가지며, 한 집합의 모든 꼭짓점이 다른 집합의 모든 꼭짓점과 연결되어 있고, 같은 집합 내의 꼭짓점끼리는 연결되지 않은 그래프이다. 이 두 그래프는 평면 상에 변이 서로 교차하지 않도록 그릴 수 없다는 것이 증명되어 있다.

쿠라토프스키 정리는 이 두 그래프를 이용해 평면 그래프의 필요충분조건을 제시한다. 정리에 따르면, 어떤 유한 그래프가 평면 그래프가 아닐 필요충분조건은 그 그래프가 K5 또는 K3,3을 부분 그래프로서 포함하거나, 이 두 그래프 중 하나를 위상적으로 동일한 형태로 포함하는 것이다. 이는 평면성 판정의 강력한 이론적 근거가 된다.

이러한 성질 때문에 K5와 K3,3은 그래프 이론에서 '금지된 소그래프'로 불리기도 한다. 이 두 그래프의 구조는 회로 설계나 네트워크 레이아웃과 같은 응용 분야에서 배선의 교차를 피하기 위한 설계 제약 조건을 이해하는 데도 중요한 통찰을 제공한다.

4색 정리는 평면 그래프 이론에서 가장 유명한 정리 중 하나이다. 이 정리는 평면 상에 그려진 어떤 지도라도 인접한 영역이 서로 다른 색을 갖도록 하기 위해 최대 네 가지 색만으로 칠할 수 있다는 내용을 담고 있다. 여기서 '인접하다'는 것은 공통된 경계선을 가진다는 의미이며, 단순히 한 점에서 만나는 경우는 포함하지 않는다.

이 문제는 1852년 프랜시스 거스리가 제기한 이후로 오랜 세월 동안 미해결 문제로 남아 있었다. 많은 수학자들이 증명을 시도했으며, 1976년 케네스 아펠과 볼프강 하켄이 컴퓨터의 도움을 받아 최초로 증명에 성공했다. 그들의 증명은 수천 가지의 특수한 경우를 컴퓨터로 일일이 검증하는 방식을 사용했기 때문에, 당시로서는 논란의 여지가 있는 혁신적인 방법이었다.

4색 정리는 순수 그래프 이론의 문제로 시작했지만, 그 응용 범위는 매우 넓다. 가장 직접적인 응용 분야는 지도 제작과 지도 색칠하기이다. 또한 회로 설계에서 서로 교차하지 않아야 하는 회로 배선을 배치하거나, 시간표 작성 문제, 자원 할당 문제 등 다양한 조합 최적화 문제를 해결하는 데에도 활용된다.

이 정리는 평면 그래프의 색칠수와 밀접한 관련이 있다. 색칠수란 그래프의 꼭짓점을 인접한 꼭짓점끼리 다른 색이 되도록 칠하는 데 필요한 최소 색의 수를 말한다. 4색 정리는 모든 평면 그래프의 색칠수가 4 이하임을 보장한다. 이는 완전 그래프 K5가 평면 그래프가 아님을 보여주는 쿠라토프스키 정리와 함께 평면 그래프의 구조적 특성을 이해하는 데 중요한 기초가 된다.

평면성 검사 알고리즘은 주어진 그래프가 평면 그래프인지, 즉 평면 상에 변이 서로 교차하지 않도록 그릴 수 있는지 판별하는 알고리즘이다. 이 문제는 그래프 이론과 알고리즘 이론의 중요한 주제로, 쿠라토프스키 정리는 이론적 판별 기준을 제공하지만 직접적인 알고리즘으로 구현하기에는 어려움이 있다.

실제 알고리즘은 주로 깊이 우선 탐색(DFS)과 이중 그래프의 개념을 활용한다. 대표적인 알고리즘으로는 1974년 존 홉크로프트와 로버트 타잔이 제안한 선형 시간 알고리즘이 있으며, 이는 그래프를 이중 연결 요소로 분해하고 각 요소가 평면 그래프의 기본 구성 요소인 삼각분할 그래프의 일부인지 확인하는 방식을 사용한다. 또 다른 접근법으로는 1999년 발표된 보이어와 마이롤드의 알고리즘이 있는데, 이는 변 추가 방식을 통해 점진적으로 평면 임베딩을 구성해 나간다.

이러한 알고리즘의 복잡도와 구현 난이도는 다음과 같이 비교할 수 있다.

평면성 검사 알고리즘은 회로 설계나 지도 색칠하기 문제를 해결하는 소프트웨어의 핵심 모듈로 활용되며, 네트워크 레이아웃을 자동으로 생성하는 도구의 기반이 되기도 한다.

평면 그래프의 평면 임베딩 알고리즘은 주어진 그래프가 평면 그래프일 경우, 변들이 서로 교차하지 않도록 평면에 실제로 그리는 방법을 찾는 알고리즘을 의미한다. 이는 단순히 평면성 여부만을 판단하는 평면성 검사 알고리즘과 구분된다. 이러한 알고리즘은 회로 설계나 네트워크 토폴로지 설계와 같이 실제 배치가 필요한 응용 분야에서 직접적으로 활용된다.

대표적인 평면 임베딩 알고리즘은 깊이 우선 탐색을 기반으로 한다. 이 알고리즘은 그래프를 순회하면서 각 꼭짓점과 변을 평면에 배치하는 순서와 위치를 결정한다. 핵심은 그래프를 이중 연결 요소로 분해하고, 각 구성 요소를 재귀적으로 처리하며, 현재까지 구성된 임베딩에 새로운 경로나 서브그래프를 교차 없이 삽입할 수 있는 위치를 찾는 것이다. 이 과정에서 각 변이 속할 면을 관리하는 자료 구조가 중요하게 사용된다.

이러한 알고리즘들은 이론적으로 선형 시간 복잡도를 가지며, 효율적으로 동작한다. 그러나 구현은 상당히 복잡한 편이며, 그래프의 평면 임베딩은 일반적으로 유일하지 않다. 즉, 동일한 그래프라도 변의 배치나 면의 모양이 다른 여러 평면 그림을 가질 수 있다는 점이 알고리즘 설계와 결과 해석에 고려되어야 한다.

회로 설계는 평면 그래프 이론이 실질적으로 응용되는 대표적인 분야이다. 특히 인쇄 회로 기판이나 집적 회로의 배선 설계에서, 서로 다른 신호선들이 서로 교차하지 않도록 배치하는 문제는 평면 그래프의 평면성 판정 및 평면 임베딩 문제와 직접적으로 연결된다. 회로의 각 소자를 꼭짓점으로, 소자 간의 연결을 변으로 모델링했을 때, 이 그래프가 평면 그래프라면 단일 층 상에서 모든 배선을 교차 없이 배치할 수 있음을 의미한다. 이는 생산 비용을 절감하고 신호 간 간섭을 줄이는 데 핵심적이다.

만약 회로의 토폴로지 그래프가 평면 그래프가 아닌 것으로 판명되면, 설계자는 여러 가지 방법으로 문제를 해결해야 한다. 가장 일반적인 방법은 비아를 이용해 서로 교차해야 하는 선 중 하나를 다른 층으로 옮기는 것이다. 이는 그래프를 다중 평면에 임베딩하는 개념으로 확장된다. 다른 방법으로는 배선 경로를 최적화하여 교차를 피하거나, 쿠라토프스키 정리에 따라 그래프에서 완전 그래프 K5나 완전 이분 그래프 K3,3와 같은 비평면적인 부분 구조를 제거하거나 변형하는 것이다.

평면 그래프 이론은 회로 설계의 자동화 도구 개발에도 기여한다. 평면성 검사 알고리즘과 평면 임베딩 알고리즘은 EDA 소프트웨어의 핵심 요소로 통합되어, 설계자가 복잡한 배선 레이아웃을 효율적으로 생성하고 검증할 수 있도록 돕는다. 이를 통해 고밀도, 고성능의 전자 장치 설계가 가능해졌다.

평면 그래프 이론의 가장 유명한 응용 분야 중 하나는 지도 색칠하기 문제이다. 이 문제는 인접한 나라나 지역이 서로 다른 색을 갖도록 지도를 색칠하는 데 필요한 최소 색의 수를 구하는 것이다. 지도의 각 영역을 꼭짓점으로, 인접한 영역 사이에 변을 그리면, 지도는 하나의 평면 그래프로 모델링될 수 있다. 따라서 지도 색칠 문제는 평면 그래프의 꼭짓점 색칠 문제로 환원된다.

이 문제를 해결한 것이 유명한 4색 정리이다. 이 정리는 평면 상의 어떤 지도라도 인접한 영역이 서로 다른 색이 되도록 색칠하는 데 네 가지 색만으로 충분하다는 것을 주장한다. 이 정리는 19세기 중반에 제기된 후 100년 이상 미해결 문제로 남아 있다가, 1976년에 케네스 아펠과 볼프강 하켄에 의해 컴퓨터를 이용한 증명이 이루어졌다. 이 증명은 수학적 증명에 컴퓨터를 본격적으로 활용한 최초의 사례로 기록되었다.

4색 정리는 평면 그래프의 특수한 성질을 보여준다. 일반적인 그래프의 경우 필요한 색의 수는 그래프 색칠수로 정의되며, 이는 그래프가 포함하는 가장 큰 완전 그래프의 크기보다 클 수 있다. 그러나 평면 그래프는 구조적 제약이 강해, 완전 그래프 K5나 완전 이분 그래프 K3,3을 포함할 수 없으며, 이로 인해 색칠수가 4 이하로 제한되는 것이다.

이러한 지도 색칠 이론은 실제 지리 정보 시스템을 넘어, 다양한 스케줄링 문제나 자원 할당 문제에 응용된다. 예를 들어, 서로 충돌하지 않도록 회의 시간을 배정하거나, 무선 통신에서 인접한 채널이 간섭하지 않도록 주파수를 할당하는 문제 등은 모두 그래프 색칠 문제로 모델링할 수 있다.

평면 그래프는 네트워크 레이아웃 설계에 있어 중요한 이론적 기반을 제공한다. 네트워크의 구성 요소를 꼭짓점으로, 이들 간의 연결 관계를 변으로 모델링한 그래프가 평면 그래프라면, 이는 물리적 배치 시 선들이 서로 교차하지 않는 깔끔한 배치가 가능함을 의미한다. 이는 복잡한 회로 기판 설계, 도로망 계획, 소셜 네트워크 분석의 시각화 등 다양한 분야에서 레이아웃의 가독성과 효율성을 극대화하는 데 활용된다.

특히 VLSI 설계와 같은 집적 회로 배치 및 배선 문제에서 평면성은 핵심 고려 사항이다. 수많은 논리 소자와 그 사이의 전기적 연결을 그래프로 표현했을 때, 이 그래프가 평면 그래프라면 여러 층의 배선 없이도 단일 평면 상에서 모든 연결을 교차 없이 구현할 수 있다. 이는 제조 공정을 단순화하고 비용을 절감하는 데 기여한다. 평면성 검사 알고리즘은 이러한 설계 단계에서 필수적인 도구로 사용된다.

네트워크 레이아웃을 최적화하는 많은 알고리즘은 평면 그래프의 성질을 이용한다. 예를 들어, 강한 평면성을 만족하는 그래프는 모든 변이 직선분으로 그려질 수 있어 레이아웃이 더욱 단순해진다. 또한, 평면 그래프의 이중 그래프 개념은 원래 네트워크와 그 위상을 서로 다른 관점에서 분석할 수 있는 틀을 제공하여, 네트워크의 흐름이나 영역 구분 문제를 해결하는 데 응용된다.

이중 그래프는 주어진 평면 그래프로부터 자연스럽게 파생되는 또 다른 평면 그래프이다. 원래 그래프의 각 면에 대응하는 꼭짓점을 생성하고, 원래 그래프에서 두 면이 변을 공유할 때마다 두 대응 꼭짓점을 변으로 연결함으로써 구성된다. 이 과정은 원래 그래프의 면과 변의 관계를 꼭짓점과 변의 관계로 변환한다.

이중 그래프의 중요한 성질 중 하나는 원래 그래프가 연결된 평면 그래프일 경우, 그 이중 그래프 또한 연결된 평면 그래프가 된다는 점이다. 또한, 이중 그래프의 이중 그래프는 원래 그래프와 위상동형이 된다. 이 개념은 그래프 이론과 위상수학에서 그래프의 구조적 특성을 연구하는 데 유용하게 활용된다.

이중 그래프는 특히 지도 색칠하기 문제와 밀접한 관련이 있다. 지도에서 각 나라를 꼭짓점으로, 국경을 공유하는 나라 사이를 변으로 연결한 그래프는 원래 지도의 이중 그래프의 개념과 일치한다. 따라서 지도 색칠 문제는 이중 그래프의 꼭짓점 색칠 문제로 환원되어, 유명한 4색 정리의 핵심적인 배경이 된다.

이러한 대응 관계를 통해 평면 그래프의 여러 조합적 성질을 다른 관점에서 분석할 수 있으며, 회로 설계나 네트워크 레이아웃과 같은 응용 분야에서도 간접적으로 그 개념이 사용된다.

평면 그래프에서 면은 그래프를 평면에 그렸을 때, 변들로 둘러싸인 영역을 의미한다. 이때 그래프의 바깥쪽 무한히 펼쳐진 영역도 하나의 면으로 포함하여 계산한다. 면의 개념은 평면 그래프의 구조를 이해하는 데 핵심적이며, 특히 오일러 공식에서 꼭짓점, 변과 함께 중요한 요소로 등장한다.

면은 변들로 구성된 경계를 가지며, 이 경계를 이루는 변의 수를 그 면의 차수라고 정의한다. 예를 들어, 삼각형으로 둘러싸인 면의 차수는 3이다. 모든 평면 그래프에서 모든 면의 차수의 합은 변의 수의 두 배와 같다는 관계가 성립한다. 이는 각 변이 정확히 두 개의 면의 경계에 속하기 때문이다.

평면 그래프의 중요한 성질 중 하나는 이중 그래프를 구성할 수 있다는 점이다. 이중 그래프는 원래 그래프의 각 면에 새로운 꼭짓점을 배치하고, 인접한 면 사이에 변을 그어 만든다. 이 과정에서 원래 그래프의 면은 이중 그래프의 꼭짓점이 되며, 이는 평면 그래프 이론과 지도 색칠하기 문제를 연결하는 중요한 개념이 된다.

평면 그래프에서 차수는 일반적인 그래프 이론에서의 정의와 동일하게, 한 꼭짓점에 연결된 변의 수를 의미한다. 그러나 평면 그래프는 평면에 임베딩된 구조를 가지므로, 이와 관련된 몇 가지 특별한 차수 개념이 추가로 존재한다.

첫 번째는 면의 차수이다. 평면 그래프에서 면의 차수는 그 면의 경계를 이루는 변의 수로 정의된다. 이때, 같은 변이 양쪽 면에 걸쳐 있다면 각 면의 경계를 셀 때 그 변을 두 번 세어야 한다. 예를 들어, 삼각형으로 둘러싸인 면의 차수는 3이다. 모든 면의 차수가 3인 평면 그래프를 삼각분할 그래프라고 부른다.

두 번째 중요한 개념은 이중 그래프의 차수와의 관계이다. 모든 연결된 평면 그래프 G에는 그에 대응되는 이중 그래프 G*가 존재한다. 이때, 원래 그래프 G의 어떤 면 f의 차수가 d라면, 이중 그래프 G*에서는 f에 대응되는 꼭짓점 v_f의 차수 역시 d가 된다. 이 관계는 평면 그래프의 구조적 특성을 분석하는 데 유용하게 활용된다.

평면 그래프에서 꼭짓점, 변, 면의 수와 차수 사이에는 오일러 공식을 통해 유도되는 여러 합 공식이 성립한다. 대표적으로, 모든 꼭짓점의 차수를 합한 값은 변의 수의 두 배와 같으며, 모든 면의 차수를 합한 값 역시 변의 수의 두 배와 같다. 이러한 관계는 평면 그래프가 가져야 하는 제약 조건을 제공하며, 4색 정리와 같은 중요한 정리들의 증명에 기초가 된다.